class GraphNode {
    name: string
    node: cc.Node
    neighbours: GraphNode[] = []
    parent: GraphNode
    cost: number = 0
    targetList: GraphNode[] = []

    constructor(name: string, node: cc.Node) {
        this.name = name
        this.node = node

        if (!node) {
            console.error(`需要 cc.Node, ${name}`)
        }
    }

    addNeighbour(node: GraphNode) {
        if (this.neighbours.indexOf(node) == -1) {
            this.neighbours.push(node)
        } else {
            console.log('重复添加节点')
        }
    }
}


class UndirectedGraph {
    nodeMap = new Map<string, GraphNode>()

    addVertex(name: string, node: cc.Node) {
        const n = new GraphNode(name, node)
        this.nodeMap.set(name, n)
    }

    addEdge(name1, name2) {
        const n1 = this.nodeMap.get(name1)
        const n2 = this.nodeMap.get(name2)

        if (!n1 || !n2) {
            return console.log(`不存在节点 ${n2 ? name1 : name2}`)
        }

        n1.addNeighbour(n2)
        n2.addNeighbour(n1)
    }

    nodeToPath(node: GraphNode) {
        const pathList = []
        let cur = node

        while (cur) {
            pathList.unshift(cur)
            cur = cur.parent
        }

        return pathList
    }

    findPath(beginName, endName) {
        const startNode = this.nodeMap.get(beginName)
        const endNode = this.nodeMap.get(endName)
        const closeList = []
        const openList = [startNode]

        startNode.parent = null
        endNode.parent = null

        while (openList.length > 0) {
            const cur = openList.pop()

            closeList.push(cur)

            for (let i = 0; i < cur.neighbours.length; i++) {
                const nb = cur.neighbours[i]

                if (closeList.indexOf(nb) == -1) {
                    nb.parent = cur
                    nb.cost = cur.cost + 1
                    openList.push(nb)

                }

                if (nb == endNode) {
                    nb.targetList.push(cur)
                }
            }

            openList.sort((a, b) => b.cost - a.cost) // 优化：应该用插入排序去维护 openList，不应该每次都重新排序
        }

        for (let i = 0; i < endNode.targetList.length; i++) {
            const target = endNode.targetList[i]

            if (endNode.parent) {
                if (endNode.parent.cost > target.cost) {
                    endNode.parent = target
                }
                // console.log(target.cost)
            } else {
                endNode.parent = target
            }

        }

        return this.nodeToPath(endNode)
    }

}

export default UndirectedGraph